#pragma once

#include<iostream>
#include<vector>
#include<ctime>
#include<cassert>
#include<cstring>
#include<thread>
#include<mutex>
#include<algorithm>
#include<unordered_map>
#include<atomic>
#include<cstdint>
#include<cstddef>
using std::cout;
using std::endl;

static const size_t MAX_BYTES=256*1024;//能向thread cache申请的最大字节数
static const size_t NFREELISTS=208;//thread cache和central cache中哈希桶个数
static const size_t NPAGES=129;//page cache中哈希桶个数
static const size_t PAGE_SHIFT=13;//页大小为8k
#ifdef _WIN64
#include<thread>
#include <Windows.h>
        typedef unsigned long long PAGE_ID;//页id
#elif _WIN32
#include<thread>
#include <Windows.h>
        typedef size_t PAGE_ID;
#else
#include<pthread.h>
#include <sys/mman.h>
        typedef unsigned long long PAGE_ID;//页id
#endif

inline static void* SystemAlloc(size_t kpage)//向系统申请若干页内存
{
#if defined(_WIN32)||defined(_WIN64)
    void* ptr=VirtualAlloc(NULL, kpage<< PAGE_SHIFT, MEM_COMMIT|MEM_RESERVE, PAGE_READWRITE);
#else
    void* ptr=mmap(NULL, kpage<< PAGE_SHIFT, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
#endif
    if(ptr==nullptr)
    {
        throw std::bad_alloc();
    }
    return ptr;
}
inline static void SystemFree(void* ptr,size_t kpage)//归还若干页内存
{
#if defined(_WIN32)||defined(_WIN64)
    VirtualFree(ptr,0, MEM_RELEASE);
#else
    int _munmap=munmap(ptr, kpage<< PAGE_SHIFT);

    if(_munmap==-1)
    {
        throw std::runtime_error("SystemFree error");
    }
#endif   
}

static void*& NextObj(void* ptr)//获取下一个对象的地址
{
   return (*(void**)ptr); 
}

class FreeList//管理切分好的小对象的自由链表
{
public:
    void Push(void* obj)//将释放的对象插入到链表头部
    {
        assert(obj);
        NextObj(obj)=_freeList;
        _freeList=obj;
        ++_size;
    }
    void* Pop()//从链表头部取出一个对象
    {
        assert(_freeList);
        void* obj=_freeList;
        _freeList=NextObj(_freeList);
        _size--;
        return obj;
    }
    void PushRange(void* start,void* end,size_t n)//将一段范围的对象插入到链表
    {
        assert(start);
        assert(end);

        NextObj(end)=_freeList;
        _freeList=start;
        _size+=n;
    }
    void PopRange(void*& start,void*& end,size_t n)//将一段范围的对象从链表取出
    {
        assert(_size>=n);
        start=_freeList;
        end=start;
        for(size_t i=0;i<n-1;++i)
        {
            end=NextObj(end);
        }
        _freeList=NextObj(end);
        NextObj(end)=nullptr;
        _size-=n;
    }
    bool Empty()//判空
    {
        return _freeList==nullptr;
    }
    size_t& MaxSize()//慢调节算法
    {
        return _maxSize;
    }
    size_t Size()//当前链表大小
    {
        return _size;
    }
private:
    void* _freeList=nullptr;//链表头指针
    size_t _maxSize=1;//慢调节算法
    size_t _size=0;//当前链表大小
};

class SizeClass//管理对齐和映射
{
public:
        //[1,128]              8byte对齐       freelist[0,16)
        //[128+1,1024]         16byte对齐      freelist[16,72)
        //[1024+1,8*1024]      128byte对齐     freelist[72,128)
        //[8*1024+1,64*1024]   1024byte对齐    freelist[128,184)
        //[64*1024+1,256*1024] 8*1024byte对齐  freelist[184,208)
        static inline size_t _RoundUp(size_t bytes,size_t alignNum)//子函数，向上对齐
        {
            return ((bytes+alignNum-1)&~(alignNum-1));
        }
        static inline size_t RoundUp(size_t bytes)//向上对齐
        {
            if(bytes<=128)
            {
                return _RoundUp(bytes,8);
            }
            else if(bytes<=1024)
            {
                return _RoundUp(bytes,16);
            }
            else if(bytes<=8*1024)
            {
                return _RoundUp(bytes,128);
            }
            else if(bytes<=64*1024)
            {
                return _RoundUp(bytes,1024);
            }
            else if(bytes<=256*1024)
            {
                return _RoundUp(bytes,8*1024);
            }
            else
            {
                return _RoundUp(bytes,1<<PAGE_SHIFT);//大于256k，按页对齐
            }
        }

        static inline size_t _Index(size_t bytes,size_t alighShift) //获取索引
        {
            return ((bytes+(1<<alighShift)-1)>>alighShift)-1;
        }
        static inline size_t Index(size_t bytes)//获取索引
        {
            static size_t groupArray[4]={16,56,56,56};
            if(bytes<=128)
            {
                return _Index(bytes,3);
            }
            else if(bytes<=1024&&bytes>128)
            {
                return _Index(bytes,4)+groupArray[0];
            }
            else if(bytes<=8*1024&&bytes>1024)
            {
                return _Index(bytes,7)+groupArray[0]+groupArray[1];
            }
            else if(bytes<=64*1024&&bytes>8*1024)
            {
                return _Index(bytes,10)+groupArray[0]+groupArray[1]+groupArray[2];
            }
            else if(bytes<=256*1024&&bytes>64*1024)
            {
                return _Index(bytes,13)+groupArray[0]+groupArray[1]+groupArray[2]+groupArray[3];
            }
            else
            {
                assert(false);
                return -1;
            }
        }
        static size_t NumMoveSize(size_t size)//threadcache一次从central cache获取对象上限
        {
            assert(size>0);
            int num=MAX_BYTES/size;
            if(num<2)
            {
                num=2;
            }
            if(num>512)
            {
                num=512;
            }
            return num;
        }
        static size_t NumMovePage(size_t size)//centralcache一次从page cache获取页数上限
        {
            size_t num=NumMoveSize(size);
            size_t nPage=num*size;//num个size大小对象所需要字节
            nPage>>=PAGE_SHIFT;//将字节数转换为页数
            if(nPage==0)
            {
                nPage=1;
            }
            return nPage;
        }
};


template<class T>
class ObjectPool//对象池
{
public:
    T* New()//申请一个对象
    {
        T* obj=nullptr;
        if(_freeList!=nullptr)
        {
            obj=(T*)_freeList;
            _freeList=NextObj(_freeList);
        }
        else
        {
           
            size_t objSize=sizeof(T)<sizeof(void*)? sizeof(void*):sizeof(T);
            if(_remainBytes<objSize)
            {
                _remainBytes=128*1024;
                //_memory=(char*)malloc(_remainBytes);
                _memory=(char*)SystemAlloc(_remainBytes>>13);
                if(_memory==nullptr)
                {
                    throw std::bad_alloc();
                }

            }
            obj=(T*)_memory;
            _memory+=objSize;
            _remainBytes-=objSize;
        }
        new(obj)T;//定位new 初始化对象
        return obj;
    }
    void Delete(T* obj)//释放一个对象
    {
        obj->~T();
        NextObj(obj)=_freeList;
        _freeList=obj;
    }
private:
    char* _memory =nullptr;//指向大块内存的指针
    size_t _remainBytes =0;//大块内存在切分过程剩余字节数
    void* _freeList =nullptr;//还回来过程中链接的自由链表的头指针
};

struct Span//管理以页为单位的大块内存
{
    PAGE_ID _pageId = 0;//起始页的页号
    size_t _n = 0;//页数

    Span* _next = nullptr;//双链表结构
    Span* _prev = nullptr;

    size_t _objSize = 0;//切好的小对象大小
    size_t _useCount = 0;//已使用的小对象个数
    void* _freeList = nullptr;//切好的小块内存的自由链表

    bool _isUse = false;//是否正在被使用
};

class SpanList//管理Span的双链表
{
public:
    SpanList()
    {
        //_head=new Span;
        _head=_spanPool.New();
        _head->_next=_head;
        _head->_prev=_head;
    }
    Span* Begin()
    {
        return _head->_next;
    }
    Span* End()
    {
        return _head;
    }
    bool Empty()
    {
        return _head->_next==_head;
    }
    void PushFront(Span* span)//头插
    {
        Insert(Begin(),span);
    }
    void* PopFront()//头删
    {
        Span* front=_head->_next;
        Erase(front);
        return front;
    }
    void Insert(Span* pos,Span* newSpan)//在pos前插入newSpan
    {
        assert(pos);
        assert(newSpan);

        Span* prev=pos->_prev;

        prev->_next=newSpan;
        newSpan->_prev=prev;

        newSpan->_next=pos;
        pos->_prev=newSpan;
    }
    void Erase(Span* pos)//删除pos
    {
        assert(pos);
        assert(pos!=_head);//不能删除头节点

        Span* prev=pos->_prev;
        Span* next=pos->_next;

        prev->_next=next;
        next->_prev=prev;
    }
private:
    Span* _head;//双链表头指针
    static ObjectPool<Span> _spanPool;//Span对象池
public:
    std::mutex _mtx;//桶锁
};
//struct Span
//{
//    PAGE_ID _pageId = 0;
//    size_t _n = 0;
//
//    std::atomic<Span*> _next = nullptr;
//    std::atomic<Span*> _prev = nullptr;
//
//    size_t _objSize = 0;
//    size_t _useCount = 0;
//    void* _freeList = nullptr;
//
//    std::atomic<bool> _isUse = false;
//};
//class SpanList
//{
//public:
//    SpanList()
//    {
//        //_head=new Span;
//        _head = _spanPool.New();
//        _head->_next.store(_head, std::memory_order_relaxed);
//        _head->_prev.store(_head, std::memory_order_relaxed);
//    }
//    Span* Begin()
//    {
//        return _head->_next.load(std::memory_order_acquire);
//    }
//    Span* End()
//    {
//        return _head;
//    }
//    bool Empty()
//    {
//        return _head->_next.load(std::memory_order_acquire) == _head;
//    }
//    void PushFront(Span* span)//头插
//    {
//        Insert(Begin(), span);
//    }
//    void* PopFront()//头删
//    {
//        Span* front = _head->_next;
//        Erase(front);
//        return front;
//    }
//    void Insert(Span* pos, Span* newSpan)//在pos前插入newSpan
//    {
//        assert(pos);
//        assert(newSpan);
//
//        // 设置新节点的前后指针
//        newSpan->_next.store(pos, std::memory_order_relaxed);
//
//        // 使用 CAS 操作插入新节点
//        while (true) {
//            Span* prev = pos->_prev.load(std::memory_order_acquire);
//            newSpan->_prev.store(prev, std::memory_order_relaxed);
//
//            // 尝试将新节点插入到pos之前
//            if (prev->_next.compare_exchange_weak(
//                pos, newSpan,
//                std::memory_order_release,
//                std::memory_order_relaxed)) {
//
//                // 插入成功，更新pos的前驱指针
//                pos->_prev.store(newSpan, std::memory_order_release);
//                break;
//            }
//
//            // CAS失败，重试
//        }
//    }
//    void Erase(Span* pos)//删除pos
//    {
//        assert(pos);
//        assert(pos != _head);
//
//        // 使用 CAS 操作删除节点
//        while (true) {
//            Span* prev = pos->_prev.load(std::memory_order_acquire);
//            Span* next = pos->_next.load(std::memory_order_acquire);
//
//            // 检查节点是否已经被删除
//            if (prev->_next.load(std::memory_order_acquire) != pos ||
//                next->_prev.load(std::memory_order_acquire) != pos) {
//                return;
//            }
//
//            // 尝试更新前驱节点的next指针
//            if (prev->_next.compare_exchange_weak(
//                pos, next,
//                std::memory_order_release,
//                std::memory_order_relaxed)) {
//
//                // 前驱节点更新成功，尝试更新后继节点的prev指针
//                next->_prev.compare_exchange_strong(
//                    pos, prev,
//                    std::memory_order_release,
//                    std::memory_order_relaxed);
//                break;
//            }
//
//            // CAS失败，重试
//        }
//    }
//
//private:
//    Span* _head;
//    static ObjectPool<Span> _spanPool;
//public:
//    //std::mutex _mtx;
//};


//二层基数树
template <int BITS>
class TCMalloc_PageMap2
{
private:
    static const int ROOT_BITS = 5;                //第一层对应页号的前5个比特位
    static const int ROOT_LENGTH = 1 << ROOT_BITS; //第一层存储元素的个数
    static const int LEAF_BITS = BITS - ROOT_BITS; //第二层对应页号的其余比特位
    static const int LEAF_LENGTH = 1 << LEAF_BITS; //第二层存储元素的个数
    //第一层数组中存储的元素类型
    struct Leaf
    {
        void* values[LEAF_LENGTH];
    };
    Leaf* root_[ROOT_LENGTH]; //第一层数组
public:
    typedef uintptr_t Number;
    explicit TCMalloc_PageMap2()
    {
        memset(root_, 0, sizeof(root_)); //将第一层的空间进行清理
        PreallocateMoreMemory(); //直接将第二层全部开辟
    }
    void* get(Number k) const
    {
        const Number i1 = k >> LEAF_BITS;        //第一层对应的下标
        const Number i2 = k & (LEAF_LENGTH - 1); //第二层对应的下标
        if ((k >> BITS) > 0 || root_[i1] == NULL) //页号值不在范围或没有建立过映射
        {
            return NULL;
        }
        return root_[i1]->values[i2]; //返回该页号对应span的指针
    }
    void set(Number k, void* v)
    {
        const Number i1 = k >> LEAF_BITS;        //第一层对应的下标
        const Number i2 = k & (LEAF_LENGTH - 1); //第二层对应的下标
        assert(i1 < ROOT_LENGTH);
        root_[i1]->values[i2] = v; //建立该页号与对应span的映射
    }
    //确保映射[start,start_n-1]页号的空间是开辟好了的
    bool Ensure(Number start, size_t n)
    {
        for (Number key = start; key <= start + n - 1;)
        {
            const Number i1 = key >> LEAF_BITS;
            if (i1 >= ROOT_LENGTH) //页号超出范围
                return false;
            if (root_[i1] == NULL) //第一层i1下标指向的空间未开辟
            {
                //开辟对应空间
                static ObjectPool<Leaf> leafPool;
                Leaf* leaf = (Leaf*)leafPool.New();
                memset(leaf, 0, sizeof(*leaf));
                root_[i1] = leaf;
            }
            key = ((key >> LEAF_BITS) + 1) << LEAF_BITS; //继续后续检查
        }
        return true;
    }
    void PreallocateMoreMemory()
    {
        Ensure(0, 1 << BITS); //将第二层的空间全部开辟好
    }
};
